#include "main/utils.h"
#include "lib/binary_tree.h"
using namespace std;

class BSTIterator {
  public:
    BSTIterator(BinaryTreeNode* root) :
      cur_node_(root) {};

    bool hasNext() {
      return (cur_node_ || !stack_help.empty());
    }

    BinaryTreeNode* next() {
      while (cur_node_) {
        stack_help.push(cur_node_);
        cur_node_ = cur_node_->left;
      }
      cur_node_ = stack_help.top();
      stack_help.pop();
      next_node_ = cur_node_;
      cur_node_ = cur_node_->right;
      return next_node_;
    }

  private:
    BinaryTreeNode* cur_node_;
    BinaryTreeNode* next_node_;
    stack<BinaryTreeNode*> stack_help;
};

class BSTReverseIterator {
  public:
    BSTReverseIterator(BinaryTreeNode* root) :
      cur_node_(root) {};

    bool hasNext() {
      return (cur_node_ || !stack_help.empty());
    }

    BinaryTreeNode* next() {
      while (cur_node_) {
        stack_help.push(cur_node_);
        cur_node_ = cur_node_->right;
      }
      cur_node_ = stack_help.top();
      stack_help.pop();
      next_node_ = cur_node_;
      cur_node_ = cur_node_->left;
      return next_node_;
    }

  private:
    BinaryTreeNode* cur_node_;
    BinaryTreeNode* next_node_;
    stack<BinaryTreeNode*> stack_help;
};

bool findNode(BinaryTreeNode* root, const int &target) {
  BSTIterator begin(root);
  BSTReverseIterator end(root);
  auto begin_node = begin.next();
  auto end_node = end.next();
  while (begin_node->value < end_node->value) {
    if (begin_node->value + end_node->value == target) {
      return true;
    } else if (begin_node->value + end_node->value < target) {
      begin_node = begin.next();
    } else {
      end_node = end.next();
    }
  }
  return false;
}

bool findNode1(BinaryTreeNode* root, const int& target) {
  set<int> help_set;
  stack<BinaryTreeNode*> help_stack;
  auto cur_node = root;
  while (cur_node || !help_stack.empty()) {
    while (cur_node) {
      help_stack.push(cur_node);
      cur_node = cur_node->left;
    }
    cur_node = help_stack.top();
    help_stack.pop();
    int find_value = target - cur_node->value;
    if (help_set.find(find_value) != help_set.end()) {
      return true;
    }
    help_set.insert(cur_node->value);
    cur_node = cur_node->right;
  }
  return false;
}

int main() {
  vector<int> vec = {8, 6, 10, 5, 7, 9, 11};
  BinaryTreeNode* root = CreateBinaryTree(vec);
  cout << findNode(root, 12) << endl;
  cout << findNode1(root, 12) << endl;

  return 0;
}
